/*
 * Copyright 2010 Christoph Widulle (christoph.widulle@googlemail.com)
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */



package com.android1.amarena2d.commons.collections;

import java.util.Arrays;
import java.util.Comparator;


public class FixedSizeArray<T> implements ReadOnlyCollectionAccess<T> {

    private final static int LINEAR_SEARCH_CUTOFF = 16;
    private final T[] mContents;
    private int mCount;
    private Comparator<T> mComparator;
    private boolean mSorted;
    private Sorter<T> mSorter;

    private int cur;

    public FixedSizeArray(int size) {
        mContents = (T[]) new Object[size];
        mCount = 0;
        mSorted = false;

        mSorter = new StandardSorter<T>();
    }

    public FixedSizeArray(int size, Comparator<T> comparator) {
        super();
        assert size > 0;
        mContents = (T[]) new Object[size];
        mCount = 0;
        mComparator = comparator;
        mSorted = false;

        mSorter = new StandardSorter<T>();
    }

    /**
     * Inserts a new object into the array.  If the array is full, an assert is thrown and the
     * object is ignored.
     */
    public final boolean add(T object) {
        if (mCount < mContents.length) {
            mContents[mCount] = object;
            mSorted = false;
            mCount++;
            return true;
        }
        return false;
    }

    /**
     * Searches for an object and removes it from the array if it is found.  Other indexes in the
     * array are shifted up to fill the space left by the removed object.  Note that if
     * ignoreComparator is set to true, a linear search of object references will be performed.
     * Otherwise, the comparator set on this array (if any) will be used to find the object.
     */
    public void remove(T object, boolean ignoreComparator) {
        final int index = find(object, ignoreComparator);
        if (index != -1) {
            remove(index);
        }
    }

    public void remove(T object) {
        this.remove(object, false);
    }

    /**
     * Removes the specified index from the array.  Subsequent entries in the array are shifted up
     * to fill the space.
     */
    public void remove(int index) {
        if (index >= mCount)
            throw new ArrayIndexOutOfBoundsException();
//        // ugh
//        if (index < mCount) {
//            for (int x = index; x < mCount; x++) {
//                if (x + 1 < mContents.length && x + 1 < mCount) {
//                    mContents[x] = mContents[x + 1];
//                } else {
//                    mContents[x] = null;
//                }
//            }
//            mCount--;
//        }

        final int numMoved = mCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(mContents, index + 1, mContents, index, numMoved);
        mContents[--mCount] = null;

    }

    /**
     * Removes the last element in the array and returns it.  This method is faster than calling
     * remove(count -1);
     *
     * @return The contents of the last element in the array.
     */
    public T removeLast() {
        T object = null;
        if (mCount > 0) {
            object = mContents[mCount - 1];
            mContents[mCount - 1] = null;
            mCount--;
        }
        return object;
    }

    /**
     * Swaps the element at the passed index with the element at the end of the array.  When
     * followed by removeLast(), this is useful for quickly removing array elements.
     */
    public void swapWithLast(int index) {
        if (mCount > 0 && index < mCount - 1) {
            T object = mContents[mCount - 1];
            mContents[mCount - 1] = mContents[index];
            mContents[index] = object;
            mSorted = false;
        }
    }

    /**
     * Sets the value of a specific index in the array.  An object must have already been added to
     * the array at that index for this command to complete.
     */
    public void set(int index, T object) {
        assert index < mCount;
        if (index < mCount) {
            mContents[index] = object;
        }
    }

    /**
     * Clears the contents of the array, releasing all references to objects it contains and
     * setting its count to zero.
     */
    public void clear() {
        for (int x = 0; x < mCount; x++) {
            mContents[x] = null;
        }
        mCount = 0;
        mSorted = false;
    }

    /**
     * Returns an entry from the array at the specified index.
     */
    public T get(int index) {
        assert index < mCount;
        if (index < mCount && index >= 0) {
            return mContents[index];
        }
        return null;
    }

    @Override
    public int find(T object) {
        return find(object, true);
    }

    @Override
    public boolean contains(T object) {
        return find(object, true) < 0;
    }

    /**
     * Returns the raw internal array.  Exposed here so that tight loops can cache this array
     * and walk it without the overhead of repeated function calls.  Beware that changing this array
     * can leave FixedSizeArray in an undefined state, so this function is potentially dangerous
     * and should be used in read-only cases.
     *
     * @return The internal storage array.
     */
    public final T[] getArray() {
        return mContents;
    }


    /**
     * Searches the array for the specified object.  If the array has been sorted with sort(),
     * and if no other order-changing events have occurred since the sort (e.g. add()), a
     * binary search will be performed.  If a comparator has been specified with setComparator(),
     * it will be used to perform the search.  If not, the default comparator for the object type
     * will be used.  If the array is unsorted, a linear search is performed.
     * Note that if ignoreComparator is set to true, a linear search of object references will be
     * performed. Otherwise, the comparator set on this array (if any) will be used to find the
     * object.
     *
     * @param object The object to search for.
     * @return The index of the object in the array, or -1 if the object is not found.
     */
    public int find(T object, boolean ignoreComparator) {
        int index = -1;
        final int count = mCount;
        final boolean sorted = mSorted;
        final Comparator comparator = mComparator;
        final T[] contents = mContents;
        if (sorted && !ignoreComparator && count > LINEAR_SEARCH_CUTOFF) {
            if (comparator != null) {
                index = Arrays.binarySearch(contents, object, comparator);
            } else {
                index = Arrays.binarySearch(contents, object);
            }
            // Arrays.binarySearch() returns a negative insertion index if the object isn't found,
            // but we just want a boolean.
            if (index < 0) {
                index = -1;
            }
        } else {
            // unsorted, linear search

            if (comparator != null && !ignoreComparator) {
                for (int x = 0; x < count; x++) {
                    final int result = comparator.compare(contents[x], object);
                    if (result == 0) {
                        index = x;
                        break;
                    } else if (result > 0 && sorted) {
                        // we've passed the object, early out
                        break;
                    }
                }
            } else {
                for (int x = 0; x < count; x++) {
                    if (contents[x] == object) {
                        index = x;
                        break;
                    }
                }
            }
        }
        return index;
    }

    public boolean contains(T object, boolean ignoreComparator) {
        return find(object, ignoreComparator) > -1;

    }

    /**
     * Sorts the array.  If the array is already sorted, no work will be performed unless
     * the forceResort parameter is set to true.  If a comparator has been specified with
     * setComparator(), it will be used for the sort; otherwise the object's natural ordering will
     * be used.
     *
     * @param forceResort If set to true, the array will be resorted even if the order of the
     *                    objects in the array has not changed since the last sort.
     */
    public void sort(boolean forceResort) {
        if (!mSorted || forceResort) {
            if (mComparator != null) {
                mSorter.sort(mContents, mCount, mComparator);
            } else {
                Arrays.sort(mContents, 0, mCount);
            }
            mSorted = true;
        }
    }

    /**
     * Returns the number of objects in the array.
     */
    public int getCount() {
        return mCount;
    }

    public int size() {
        return mCount;
    }

    public int getFreeCount() {
        return mContents.length - mCount;
    }

    /**
     * Returns the maximum number of objects that can be inserted inot this array.
     */
    public int getCapacity() {
        return mContents.length;
    }

    public boolean isFull() {
        return mCount == mContents.length;
    }

    /**
     * Sets a comparator to use for sorting and searching.
     */
    public void setComparator(Comparator<T> comparator) {
        mComparator = comparator;
        mSorted = false;
    }

    public void setSorter(Sorter<T> sorter) {
        mSorter = sorter;
    }


    public void itr() {
        this.cur = 0;
    }

    public boolean hasNext() {
        return get(cur + 1) != null;
    }

    public T next() {
        return get(cur++);
    }


}


